Symbolic ultrametrics define edge-colored complete graphs K_n and yield asimple tree representation of K_n. We discuss, under which conditions this ideacan be generalized to find a symbolic ultrametric that, in addition,distinguishes between edges and non-edges of arbitrary graphs G=(V,E) and thus,yielding a simple tree representation of G. We prove that such a symbolicultrametric can only be defined for G if and only if G is a so-called cograph.A cograph is uniquely determined by a so-called cotree. As not all graphs arecographs, we ask, furthermore, what is the minimum number of cotrees needed torepresent the topology of G. The latter problem is equivalent to find anoptimal cograph edge k-decomposition {E_1,...,E_k} of E so that each subgraph(V,E_i) of G is a cograph. An upper bound for the integer k is derived and itis shown that determining whether a graph has a cograph 2-decomposition, resp.,2-partition is NP-complete.
展开▼
